#include <stdio.h>
#include <stdlib.h>
#define M 200000
 
long _mergeSort(long arr[], long temp[],
               long left, long right);
long merge(long arr[], long temp[],
          long left, long mid,
          long right);
 
/* This function sorts the input array and returns the
   number of inversions in the array */
long mergeSort(long arr[], long array_size)
{
    long* temp = (long*)malloc(sizeof(long) * array_size);
    return _mergeSort(arr, temp, 0,
                      array_size - 1);
}
 
/* An auxiliary recursive function
   that sorts the input
  array and returns the number
  of inversions in the array.
*/
long _mergeSort(long arr[], long temp[], long left, long right)
{
    long mid, inv_count = 0;
    if (right > left)
    {
        /* Divide the array longo two parts and call
       _mergeSortAndCountInv() for each of the parts */
        mid = (right + left) / 2;
 
        /* Inversion count will be the sum of inversions in
        left-part, right-part and number of inversions in
        merging */
        inv_count += _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid + 1, right);
 
        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid + 1, right);
    }
    return inv_count;
}
 
/* This funt merges two sorted
   arrays and returns inversion
   count in the arrays.*/
long merge(long arr[], long temp[], long left, long mid,
          long right)
{
    long i, j, k;
    long inv_count = 0;
 
    i = left; /* i is index for left subarray*/
    j = mid; /* j is index for right subarray*/
    k = left; /* k is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right)) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
 
            /*this is tricky -- see above
             * explanation/diagram for merge()*/
            inv_count = inv_count + (mid - i);
        }
    }
 
    /* Copy the remaining elements of left subarray
   (if there are any) to temp*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];
 
    /* Copy the remaining elements of right subarray
   (if there are any) to temp*/
    while (j <= right)
        temp[k++] = arr[j++];
 
    /*Copy back the merged elements to original array*/
    for (i = left; i <= right; i++)
        arr[i] = temp[i];
 
    return inv_count;
}
 
/* 主函数*/
int main()
{
	/*
    long arr[] = {3,1,2};
    printf(" Number of inversions are %d \n",
           mergeSort(arr, 3));
	*/
	long a[M] = {0};
	long i, j, n;
	long x=10000000+9;
	long cc = 0;
	long all[1000];
	while(scanf("%ld", &n) != EOF)
	{
		for(i = n-1; i >= 0; i--)
		{
			scanf("%ld", &a[i]);
		}		
		all[cc] = mergeSort(a, n) % x;
		cc++;
		// memset(a,0,sizeof(a));
	}
	for (i = 0; i < cc; i++)
		printf("%ld\n", all[i]);
    return 0;
}